package demo2;

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    //1.反转链表 II(虚拟头插法)
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //思路：对要反转的链表进行头插法
        if(left == right) {
            return head;
        }
        ListNode ret = new ListNode(0);//cur的上一个结点
        ListNode prev = ret;
        prev.next = head;
        //找到cur所要指向的位置
        for(int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        ListNode cur = prev.next;
        //新思路:虚拟头插法
        for(int i = left; i < right; i++) {
            ListNode curNext = cur.next;
            cur.next = curNext.next;
            curNext.next = prev.next;//这里不能写cur，因为cur的位置时时刻刻都在变
            prev.next = curNext;
        }
        return ret.next;
    }
    //2.删除排序链表中的重复元素
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) {
            return head;
        }
        ListNode cur = head;
        ListNode curNext = head.next;
        //下一个结点若与当前结点相同，就删除,直到不相同或者为null,才往后走
        while(curNext != null) {
            if(cur.val == curNext.val) {
                cur.next = curNext.next;
                curNext = curNext.next;
            }else{
                cur = cur.next;
                curNext = cur.next;
            }
        }
        return head;
    }
    //3.回文链表(快慢指针)
    public boolean isPalindrome(ListNode head) {
        if(head.next == null) {
            return true;
        }
        //反转后半截 + 快慢指针
        ListNode fast = head;
        ListNode slow = head;
        //先求出链表长度
        int len = 0;
        while(fast != null) {
            len++;
            fast = fast.next;
        }
        fast = head;
        //让fast走到一半
        int mid = (len % 2 == 0) ? len/2 - 1 : len/2;//保证走到中间
        for(int i = 0; i < mid; i++) {
            fast = fast.next;
        }
        //反转fast后面的链表(fast可以想象成虚拟头节点)
        ListNode cur = fast.next;
        while(cur.next != null) {
            ListNode curNext = cur.next;
            cur.next = curNext.next;
            curNext.next = fast.next;
            fast.next = curNext;
        }
        fast = fast.next;
        //快慢指针一起走，发现不同就不是回文
        while(fast != null) {
            if(slow.val != fast.val) {
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }
    //3.回文链表(快慢指针(优化))
/*    public boolean isPalindrome(ListNode head) {
        if(head.next == null) {
            return true;
        }
        //反转后半截 + 快慢指针
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = slow;
        slow = head;
        //反转fast后面的链表(fast可以想象成虚拟头节点)
        ListNode cur = fast.next;
        while(cur.next != null) {
            ListNode curNext = cur.next;
            cur.next = curNext.next;
            curNext.next = fast.next;
            fast.next = curNext;
        }
        fast = fast.next;
        //快慢指针一起走，发现不同就不是回文
        while(fast != null) {
            if(slow.val != fast.val) {
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }*/
    //4.LRU 缓存 (最后一个测试无法通过)
    class LRUCache {
        //双向链表
        class ListNode {
            private ListNode next;
            private ListNode prev;
            private int key;
            private int val;
            ListNode (int key, int val) {
                this.key = key;
                this.val = val;
            }
            ListNode (){}
        }
        private Map<Integer, ListNode> map = new HashMap<>();
        private ListNode head = null;
        private ListNode tail = null;
        private int usedSize = 0;//使用空间
        private int capacity = 0;//容量
        //LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
        public LRUCache(int capacity) {
            this.capacity = capacity;
        }
        //int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
        public int get(int key) {
            if(!map.containsKey(key)) {
                return -1;
            }else {
                //这里相当于使用了结点，所以要调整位置
                int tmpValue = map.get(key).val;
                deleteNode(map.get(key));
                addTail(key, tmpValue);
                map.put(key, tail);
                return tail.val;
            }
        }
        //void put(int key, int value)如果关键字key 已经存在，
        // 则变更其数据值value ；如果不存在，则向缓存中插入该组key-value 。
        // 如果插入操作导致关键字数量超过capacity ，则应该 逐出 最久未使用的关键字
        public void put(int key, int value) {
            if(usedSize == capacity) {
                //删除头节点
                if(head != null) {
                    map.remove(head.key);
                    deleteFirst();
                }
                //尾插新的结点
                addTail(key, value);
                map.put(key, tail);
                return;
            }
            if(!map.containsKey(key)) {
                if(head == null) {
                    head = new ListNode(key, value);
                    map.put(key, head);
                    tail = head;
                }else {
                    addTail(key, value);
                    map.put(key, tail);
                }
                usedSize++;
            }else {
                //因为变更数据会使其变为最新的关键字，所以先要删除此结点，然后再尾插一个这样的结点
                map.remove(key);
                deleteNode(map.get(key));
                addTail(key, value);
                map.put(key, tail);
            }
        }

        //尾部增加结点
        private void addTail(int key, int value) {
            if(head == null) {
                head = new ListNode(key, value);
                tail = head;
            }else{
                tail.next = new ListNode(key, value);
                ListNode tmp = tail;
                tail = tail.next;
                tail.prev = tmp;
            }

        }
        //删除头节点
        private void deleteFirst() {
            head = head.next;
            if(head != null) {
                head.prev = null;
            }
        }
        //删除结点
        private void deleteNode(ListNode del) {
            if(del == head) {
                head = head.next;
                if(head != null) {
                    head.prev = null;
                }
            }else if(del == tail) {
                tail = tail.prev;
                tail.next = null;
            }else {
                del.prev.next = del.next;
                del.next.prev = del.prev;
            }
        }
    }
    //LRU 缓存 (通过)
    public class LRUCache2 {
        class DLinkedNode {
            int key;
            int value;
            DLinkedNode prev;
            DLinkedNode next;
            public DLinkedNode() {}
            public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
        }

        private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
        private int size;
        private int capacity;
        private DLinkedNode head, tail;

        public LRUCache2(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            // 使用伪头部和伪尾部节点
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head.next = tail;
            tail.prev = head;
        }

        public int get(int key) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                return -1;
            }
            // 如果 key 存在，先通过哈希表定位，再移到头部
            moveToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                // 如果 key 不存在，创建一个新的节点
                DLinkedNode newNode = new DLinkedNode(key, value);
                // 添加进哈希表
                cache.put(key, newNode);
                // 添加至双向链表的头部
                addToHead(newNode);
                ++size;
                if (size > capacity) {
                    // 如果超出容量，删除双向链表的尾部节点
                    DLinkedNode tail = removeTail();
                    // 删除哈希表中对应的项
                    cache.remove(tail.key);
                    --size;
                }
            }
            else {
                // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
                node.value = value;
                moveToHead(node);
            }
        }

        private void addToHead(DLinkedNode node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }

        private void removeNode(DLinkedNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void moveToHead(DLinkedNode node) {
            removeNode(node);
            addToHead(node);
        }

        private DLinkedNode removeTail() {
            DLinkedNode res = tail.prev;
            removeNode(res);
            return res;
        }
    }

    //5.旋转链表
    public ListNode rotateRight(ListNode head, int k) {
        //思路：创造一个虚拟结点，先对其进行后k个结点进行对虚拟节点的尾插
        //再对剩下的结点进行尾插
        //先求出长度
        if(head == null) {
            return head;
        }
        ListNode cur = head;
        int len = 0;
        while(cur != null) {
            len++;
            cur = cur.next;
        }
        if(len == 1) {
            return head;
        }
        cur = head;
        //优化长度
        if(k >= len) {
            k %= len;
        }
        ListNode node = new ListNode();//虚拟头节点
        //cur移动到倒数第k个结点的前一个结点
        for(int i = 0; i < len - k - 1; i++) {
            cur = cur.next;
        }
        //倒数k个元素的尾插
        node.next = cur.next;
        cur.next = null;
        //前k个元素的头插
        cur = node;
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = head;
        return node.next;
    }

/*    //6.删除排序链表中的重复元素 II(快慢指针)
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) {
            return head;
        }
        ListNode node = new ListNode(-1);//虚拟头节点
        node.next = head;
        ListNode prev = node;
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                ListNode tmp = cur.next;
                //找到不重复为止
                while(tmp != null && cur.val == tmp.val) {
                    tmp = tmp.next;
                }
                prev.next = tmp;
                cur = tmp;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        return node.next;
    }*/
    //7.排序链表(奇淫巧计)
    public ListNode sortList(ListNode head) {
        //奇淫巧计
        ListNode cur = head;
        List<Integer> list = new ArrayList<>();
        while(cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        Collections.sort(list);
        cur = head;
        for(int i = 0; i < list.size(); i++) {
            cur.val = list.get(i);
            cur = cur.next;
        }
        return head;
    }
    //8.分隔链表(新链表法100%,60%)
    public ListNode partition(ListNode head, int x) {
        //思路：把小于X的结点重新建在新点后面，大于的紧跟着
        ListNode node = new ListNode();//虚拟头节点
        ListNode cur = head;
        ListNode curNode = node;
        //先放小于的
        while(cur != null) {
            if(cur.val < x) {
                ListNode tmp = new ListNode(cur.val);
                curNode.next = tmp;
                curNode = tmp;
            }
            cur = cur.next;
        }
        cur = head;

        //再放大于等于的
        while(cur != null) {
            if(cur.val >= x) {
                ListNode tmp = new ListNode(cur.val);
                curNode.next = tmp;
                curNode = tmp;
            }
            cur = cur.next;
        }
        return node.next;
    }
    //8.分隔链表(新链表法（优化）)
  /*  public ListNode partition(ListNode head, int x) {
        //思路：维护俩个链表即可，一个放大的，一个放小的
        ListNode smallHead = new ListNode();//虚拟头节点
        ListNode bigHead = new ListNode();
        ListNode small = smallHead;
        ListNode big = bigHead;
        while(head != null) {
            if(head.val < x) {
                small.next = head;
                small = small.next;
            }else {
                big.next = head;
                big = big.next;
            }
            head = head.next;
        }
        big.next = null;
        small.next = bigHead.next;
        return smallHead.next;
    }*/
    //9.删除链表中的节点(我太吊了(doge)换个思路，不用修改节点连接，修改值即可)
/*    public void deleteNode(ListNode node) {
        //思路：既然改变不了结点，那就改变结点的val值
        ListNode prev = node;
        node = node.next;
        while(node.next != null) {
            prev.val = node.val;
            prev = node;
            node = node.next;
        }
        prev.val = node.val;
        prev.next = null;
    }*/
    //删除链表中的节点(逆天优化)
    public void deleteNode(ListNode node) {
        //思路：既然结点难下手，那就改变结点的val值
        //优化版
        node.val = node.next.val;
        node.next = node.next.next;
    }
    //10.重排链表(暴力头插法)
    public void reorderList(ListNode head) {
        //暴力头插法，把结尾的结点头插到前面
        ListNode cur = head;
        while(cur.next != null && cur.next.next != null) {
            ListNode tail = cur;
            ListNode prev = cur;
            while(tail.next != null) {
                prev = tail;
                tail = tail.next;
            }
            //此时tail已经到达尾部,只需要将tail结点插入cur后面即可
            tail.next = cur.next;
            cur.next = tail;
            prev.next = null;
            cur = tail.next;
        }
    }
}
